package lc695;
//给你一个大小为 m x n 的二进制矩阵 grid 。
//
// 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都
//被 0（代表水）包围着。
//
// 岛屿的面积是岛上值为 1 的单元格的数目。
//
// 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
//
//
//
// 示例 1：
//
//
//输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,
//0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,
//0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
//输出：6
//解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
//
//
// 示例 2：
//
//
//输入：grid = [[0,0,0,0,0,0,0,0]]
//输出：0
//
//
//
//
// 提示：
//
//
// m == grid.length
// n == grid[i].length
// 1 <= m, n <= 50
// grid[i][j] 为 0 或 1
//
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组 矩阵 👍 578 👎 0

import utils.IntArrTwoFactory;
import utils.TestHelperFactory;

import java.util.Arrays;

public class Solution {

    class UnionFind {

        private final int[] father;

        private final int[] rank;

        private final int[] area;

        private int ans;

        public UnionFind(int[][] grid) {
            int row = grid.length;
            int col = grid[0].length;
            ans = 0;
            father = new int[row * col];
            rank = new int[row * col];
            area = new int[row * col];
            Arrays.fill(father, 0);
            Arrays.fill(rank, 0);
            Arrays.fill(area, 1);
            unionFind(grid);
            for(int i = 0; i < row; ++i){
                for(int j = 0; j < col; ++j){
                    if(grid[i][j] == 1){
                        grid[i][j] = 0;
                        int xy = i * col + j;
                        if(i - 1 >= 0 && grid[i - 1][j] == 1){
                            union(xy, (i - 1) * col + j);
                        }
                        if(i + 1 < row && grid[i + 1][j] == 1){
                            union(xy, (i + 1) * col + j);
                        }
                        if(j - 1 >= 0 && grid[i][j - 1] == 1){
                            union(xy, xy - 1);
                        }
                        if(j + 1 < col && grid[i][j + 1] == 1){
                            union(xy, i * col + j + 1);
                        }
                    }
                }
            }
        }

        /** 按秩合并 */
        public void union(int x, int y) {
            int fx = find(x);
            int fy = find(y);
            if(fx == fy){
                return;
            }
            if(rank[fx] > rank[fy]){
                father[fy] = fx;
                area[fx] += area[fy];
            }else if(rank[fy] > rank[fx]){
                father[fx] = fy;
                area[fy] += area[fx];
            }else{
                area[fx] += area[fy];
                father[fy] = fx;
                ++rank[fx];
            }
            ans = Math.max(ans, Math.max(area[fy], area[fx]));
        }

        public void unionFind(int[][] grid) {
            int row = grid.length;
            int col = grid[0].length;
            for(int i = 0; i < row; ++i){
                for(int j = 0; j < col; ++j){
                    if(grid[i][j] == 1){
                        ans = 1;
                    }
                    int xy = i * col + j;
                    father[xy] = xy;
                }
            }
        }

        public int find(int x) {
            if(x == father[x]){
                return x;
            }
            //路径压缩
            father[x] = find(father[x]);
            return father[x];
        }

    }

    /**
     * 695. 岛屿的最大面积
     * 难度: 中等
     * time: unionFind为O(N)/find为O(logN)/union为O(logN)
     * space: O(N*L) 岛的总数
     * spend: 120m
     */
    public int maxAreaOfIsland(int[][] grid) {
        if(grid.length == 0 || grid[0].length == 0){
            return 0;
        }
        UnionFind unionFind = new UnionFind(grid);
        return unionFind.ans;
    }

    public static void main(String[] args) {
        TestHelperFactory<int[][]> testHelperFactory = new IntArrTwoFactory();
        int[][] produce = testHelperFactory.produce(
                "[[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,"
                        + "0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,"
                        + "0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]");

        int i = new Solution().maxAreaOfIsland(produce);
        System.out.println(i);
    }

}
//leetcode submit region end(Prohibit modification and deletion)
